package knapsackDp;

import java.util.Scanner;
public class  knapsackDp {
    public static void  main (String[] args) {
        // 读入数据的代码
        Scanner Sc = new Scanner(System.in);
        System.out.println("输入物品的数量和背包的最大容量使用空格隔开");
        // 物品的数量为N
        int N = Sc.nextInt();
        // 背包的最大容量为V
        int V = Sc.nextInt();
        // 一个长度为N的数组，第i个元素表示第i个物品的重量
        int[] v = new int[N + 1];

        // 一个长度为N的数组，第i个元素表示第i个物品的价值；
        int[] w = new int[N + 1];
        System.out.println("请输入物品的重量和价值使用空格隔开");
        for (int i = 1; i <= N; i++) {
            // 接下来有 N 行，每行有两个整数:v[i],w[i]，用空格隔开，分别表示第i件物品的体积和价值
            v[i] = Sc.nextInt();
            w[i] = Sc.nextInt();
        }
        int[][] dp = new int[N + 1][V + 1];
        //初始化第一行第一列数据为0
        dp[0][0] = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= V; j++) {
                //当承重量大于当前物品的重量时，放入背包计算最大价值
                if (j >= v[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
                } else {
                    //当承载量小于当前背包的重量时，不放入该物品，继承上一个最大价值
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println("输出动态规划数组dp");
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= V; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        //记录每一个物品是否被放入背包中 0为未放入，1为放入背包中，
        int [] item=new int [N+1];
        int max=V;//从最后一个元素开始,max为最大的承重力
        for(int i=N;i>0;i--){
            if(dp[i][max]==dp[i-1][max]){
                item[i]=0;
            }else{
                item[i]=1;
                max=max-v[i];
            }
        }
        System.out.print("包内额物品编号为：");
        for(int i=0;i<N+1;i++){
            if(item[i]==1){
                System.out.print(i+" ");
            }
        }
        System.out.println();
        System.out.print("包内能承载的物品最大价值为："+dp[N][V]);
    }
}